﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Topcoder
{
    namespace SRM547
    {
        class MinimalTriangle
        {
            public static double maximalArea(int length)
            {
                return 1.0 * length * length * Math.Sqrt(3) / 4;
            }
        }

        class PillarsDivTwo
        { 
            public static double maximalLength(int[] height, int w)
            {
                int sumodd = 0;
                int sumeven = 0;
                for (int i = 0; i < height.Length; i++)
                {
                    if (i % 2 == 0) sumeven += height[i];
                    else sumodd += height[i];
                }

                double max = 0;
                if (sumodd < sumeven)
                {
                    for (int i = 0; i < height.Length - 1; i++)
                    {
                        if (i % 2 == 0) max += Math.Sqrt((height[i] - 1) * (height[i] - 1) + w * w);
                        else max += Math.Sqrt((height[i + 1] - 1) * (height[i + 1] - 1) + w * w);
                    }
                }
                else if (sumodd > sumeven)
                {
                    for (int i = 0; i < height.Length - 1; i++)
                    {
                        if (i % 2 == 1) max += Math.Sqrt((height[i] - 1) * (height[i] - 1) + w * w);
                        else max += Math.Sqrt((height[i + 1] - 1) * (height[i + 1] - 1) + w * w);
                    }
                }                
                return max;
            }
        }

        class RelativelyPrimeSubset
        {
            public static int findSize(int[] S)
            {
                List<int> s = new List<int>(S);
                s.Sort();
                int len = s.Count;
                for (int i = len - 1; i > 0; i--)
                {
                    for (int j = i - 1; j >= 0; j--)
                    {
                        if (GCD(s[i],s[j]) !=  1)
                        {
                            s.RemoveAt(i);
                            break;
                        }
                    }
                }
                Console.WriteLine();
                foreach (int i in s) Console.Write("{0} ", i);
                return s.Count;
            }
            
            static int GCD(int a, int b)
            {
                int Remainder;
                while (b != 0)
                {
                    Remainder = a % b;
                    a = b;
                    b = Remainder;
                }
                return a;
            }
        }
    }
}
